package day41_52;

import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/19 20:46
 * @Version 1.0
 */
public class Solution {

    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals = new HashSet<>();
        return backtrack(n, 0, columns, diagonals);


    }

    private int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals) {
        if (row == n){
            return 1;
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (columns.contains(i)){
                continue;
            }
            int diagonal1 = row - i;
            if (diagonals.contains(diagonal1)){
                continue;
            }
            int diagonal2 = row + i;
            if (diagonals.contains(diagonal2)){
                continue;
            }
            columns.add(i);
            diagonals.add(diagonal1);
            diagonals.add(diagonal2);
            count += backtrack(n, row+ 1, columns, diagonals);
            columns.remove(i);

        }
        return count;
    }
}
